This invention relates generally to an improvement in a binary parallel multiplier, and in particular, to a parallel multiplier based on modified Booth's algorithms.
Various systems have been proposed for increasing the speed of binary parallel multipliers. An example is described in COMPUTER ARITHMETIC 1979, p129-211, John Wiley & Sons Co. and NIKKEI ELECTRONICS, May 29, 1978, P76-89.
The following is a description of a prior art parallel multiplier which is based on modified Booth's algorithms. Modified Booth's algorithms are known as one method of speeding up multiplication. These algorithms are described in detail in the above publications so a description has been omitted.
One example of the structure of the basic cell of a prior art parallel multiplier which is based on modified Booth's algorithms is shown in FIG. 1. The basic cell shown here has the same structure shown in FIG. 2 of Japan Patent Disclosure Sho 57-28129.
Data Xi, which is the ith bit of multiplicand X, is input to basic cell 1 via input terminal 3. The ith bit corresponds to the position of cell 1 of multiplicand X. Data Xi-1 which is one bit lower than Xi is input to basic cell 1 via terminal 5. Select signals S(X) and S(2X) are input via terminals 7 and 9. Data Xi and select signal S(X) are input to first AND gate 11. And data Xi-1 and select signal S(2X) are input to second AND gate 13. The output signals of these AND gates 11, 13 are input to OR gate 15, whose output signal is supplied to one of the input terminals of EXCLUSIVE OR gate 17. Control signal INV is input to the other input terminal of EX OR gate 17 via terminal 19. The output signal of EX OR gate 17 is input to the full adder 21 to which the sum of the full adder of the basic cell of the same digit in the previous row is also input via terminal 23. The carry data of the full adder one digit lower is input via terminal 25.
First and second AND gates 11, 13, and OR gate 15 form a 2-input 1-output selector. When select signal S(X) is at a high level, this selector outputs data Xi, and when select signal S(2X) is at a high level, data Xi-1 is output. When control signal INV is at a high level, EX OR gate 17 inverts the output of this selector and supplies it to full adder 21. When control signal INV is at a low level EX OR gate 17 supplies the selector output to full adder 21 without inversion. Full adder 21 outputs the sum and carry data via terminals 27 and 29, respectively.
Select signals S(X), S(2X) and control signal INV are obtained based on the following equation (1)-(3). EQU S(X)=y2i-2.sym.y2i-1 (1) EQU S(2X)=y2i.multidot.y2-1.multidot.y2i-2+y2i.multidot.y2i-1.multidot.y2i-2 (2) EQU INV=y2i (3)
where .sym. is exclusive OR, . is AND, and + is OR. Data y2i, y2i-1, y2i-2 are the continuous 3-bit data of the 2ith bit, 2i-1 bit, and 2i-2 bit of multiplier Y, and i is a positive integer.
As is generally known, parallel multipliers based on secondary Booth's algorithms have half the number of basic cell rows and half the number of cells used compared to conventional parallel multipliers. However, the number of transistors which comprise the basic cells is increased. For example, eighteen transistors are used in the input section (multiplicand control section) other than that for the full adder. Namely, if it is assumed that EX OR gate 17 is constructed of compound gate 37 (broken line 31 of FIG. 2), which comprises AND gate 33 and NOR gate 35, and NOR gate 39, ten MOS transistors are required. If compound gate 41 comprising AND gates 11, 13 as the 2 to 1 selector, and NOR gate 16 is used, eight transistors are required.
Consequently, a parallel multiplier using basic cells such as that shown in FIG. 1 has the following drawbacks: (1) Many transistors are used in each basic cell, increasing the size of the cell and decreasing integration density, which results in a large multiplier; (2) The large number of transistors increases the power consumption; (3) High integration is not possible so productivity is poor and the chip size increases; (4) Poor productivity and large chips mean a high cost multiplier; and (5) The wiring between basic cells is lengthened resulting in long signal propagation times. Also, because many transistors are used in the control section the propagation time of the multiplicand data is long resulting in slow computation speed.